package code;

//题目链接：https://leetcode.cn/problems/minimum-time-to-make-rope-colorful/?envType=daily-question&envId=2025-11-03
//时间复杂度：O(N)
public class MinCost {
	//由题知，只需要处理相邻且相同颜色的位置。注意点：同色相邻的气球可能有多个；
	//总思路：双指针
	//具体思路：指针i遍历数组，如果相邻颜色不同，统计相等气球的所有时间和以及区间最大值
	//	       sum-max，即为使这部分区间为彩色的最少时间(n个同色->1个颜色，找最大使剩余最小)
    public int minCost(String colors, int[] neededTime) {
        char[] s=colors.toCharArray();
        int ret=0;
        int n=s.length;
        for(int i=1;i<n;i++){
            //发现同色气球
            if(s[i-1]==s[i]){
                //记录删除该相邻颜色区间所有气球的时间
                int sum=neededTime[i-1]+neededTime[i];
                //记录删除该相邻颜色区间中某个气球花费的最大时间
                int min_num=Math.max(neededTime[i-1],neededTime[i]);
                //用于同色相邻区间的遍历
                int j=i+1;
                //只要区间内同色，就一直循环
                while(j<n&&s[j]==s[i]){
                    min_num=Math.max(min_num,neededTime[j]);
                    sum+=neededTime[j];
                    j++;
                }
                //n个同色->1个颜色  =》 所有时间-最长时间 =》剩余最短
                ret+=sum-min_num;
                i=j;
            }
        }
        return ret;
    }
}
